package com.leetcode.array;

import java.math.BigDecimal;
import java.util.*;

/**
 * Created by huangyugen on 2019/07/16
 *
 **/
public class Solution {

    /**
     * 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度
     * 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
     * @param nums
     * @return
     */
    public static int removeDuplicates(int[] nums) {
        //   [0,0,1,1,1,2,2,3,3,4]
        //-->[0, 1, 2, 3, 4]
        int length = 0;
        if(nums.length == 0){
            return 0;
        }
        if(nums.length == 1){
            nums[length] = nums[nums.length - 1];
            length ++;
            return length;
        }
        if(nums.length == 2){
            if(nums[0] != nums[1]){
                nums[length] = nums[0];
                length ++;
                nums[length] = nums[1];
                length ++;
            }else{
                nums[length] = nums[0];
                length ++;
            }
            return length;
        }
        //超过三个循环判断
        for (int i = 0;i < nums.length - 1;i++){
            if(nums[i] != nums[i + 1]){
                nums[length] = nums[i];
                length ++;
            }
            //判断最后一个元素是否和找出来最后一个相等
            if( i + 1 == nums.length - 1 && (length == 0 || nums[i + 1] != nums[length - 1]) ){
                nums[length] = nums[i + 1];
                length ++;
            }
        }
        return length;
    }

    /**
     * 给定一个整数数组，判断是否存在重复元素。
     * @param nums
     * @return
     * 如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。
     * 输入: [1,2,3,1]
     * 输出: true
     */
    public static boolean containsDuplicate(int[] nums) {
        if(nums.length == 0 || nums.length == 1){
            return false;
        }
//        for (int i = 0;i < nums.length - 1; i ++){
//            for (int j = i + 1;j < nums.length; j ++){
//                if(nums[i] == nums[j]){
//                    return true;
//                }
//            }
//        }

        Arrays.sort(nums);
        for (int i = 1;i < nums.length; i ++){
            if(nums[i-1] == nums[i])
                return true;
        }

        return false;
//        Set<Integer> set = new HashSet(nums.length);
//        for (int i = 0;i < nums.length; i ++){
//            set.add(nums[i]);
//        }
//        return set.size() != nums.length ;
    }

    /**
     * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
     * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
     * 输入: [2,2,1]
     * 输出: 1
     * @param nums
     * @return
     */
    public static int singleNumber(int[] nums) {
        //异或：5^5=0，5^0=5，相同的数异或得到0，与0异或得到本身
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            result = result^nums[i];
        }
        return result;
    }

    /**
     * 给定两个数组，编写一个函数来计算它们的交集
     *  nums1 = [1,2,2,1], nums2 = [2,2]
     *  ==>[2,2]
     * @param nums1
     * @param nums2
     * @return
     */
    public static int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums1) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        List<Integer> tempList = new ArrayList<>();
        for (int num : nums2) {
            if (map.containsKey(num) && map.get(num) > 0) {
                map.put(num, map.get(num) - 1);
                tempList.add(num);
            }
        }
        int[] result = new int[tempList.size()];
        for (int i = 0; i < result.length; i++) {
            result[i] = tempList.get(i);
        }
        return result;
    }

    /**
     * 给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一
     * @param digits
     * @return
     * 输入: [1,2,3]
     * 输出: [1,2,4]
     * 解释: 输入数组表示数字 123。
     */
    public static int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i] = digits[i] + 1;
                break;
            } else {
                digits[i] = 0;
            }
            if(i == 0 && digits[0] == 0){
                int[] copy = new int[digits.length + 1];
                copy[0] = 1;
                System.arraycopy(digits,1,copy,1,digits.length -1);
                digits = copy;
            }
        }
        return digits;
    }

    /**
     * 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
     * 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
     * 给定 nums = [2, 7, 11, 15], target = 9
     * 因为 nums[0] + nums[1] = 2 + 7 = 9
     * 所以返回 [0, 1]
     *
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum(int[] nums, int target) {
//        int[] temp = new int[2];
//        for (int i = 0; i < nums.length - 1; i++) {
//            temp[0] = i;
//            for (int j = i + 1; j < nums.length; j++) {
//                if (nums[i] + nums[j] == target) {
//                    temp[1] = j;
//                    return temp;
//                }
//            }
//        }
//        return temp;
//        for(int i = 0 ; i < nums.length - 1 ; i++){
//            for(int j = i + 1 ; j < nums.length ; j++){
//                if(target == nums[i]+nums[j]){
//                    return new int[]{i,j};
//                }
//            }
//        }
        HashMap map = new HashMap(nums.length);
        for (int i = 0; i < nums.length; i++) {
            int a = nums[i];
            int want =  target - a;
            if (map.containsKey(want)) {
                return new int[]{(Integer) map.get(want),i};
            }else {
                map.put(a, i);
            }
        }
        return null;
    }

    /**
     * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     * 输入: [0,1,0,3,12]
     输出: [1,3,12,0,0]
     说明:

     必须在原数组上操作，不能拷贝额外的数组。
     尽量减少操作次数。
     * @param nums
     */
    public static void moveZeroes(int[] nums){
//        for (int i = 0;i < nums.length; i++){
//            if(0 == nums[i]){
//                for (int j = i + 1;j < nums.length;j++){
//                    if(nums[j] != 0){
//                        swap(i,j,nums);
//                        i ++;
//                    }
//                }
//            }
//        }
        int i=0;
        for(int j=0;j<nums.length;j++){
            if(nums[j]!=0){
                nums[i]=nums[j];
                i++;
            }
        }
        for(;i<nums.length;i++){
            nums[i]=0;
        }
    }

    private static void swap(int i,int j,int[] num){
        int temp = num[i];
        num[i] = num[j];
        num[j] = temp;
    }




}
